package com.zwy.leetcode;

import java.util.Stack;

public class LinkListTest {

    public static void main(String[] args) {
        LinkListTest test=new LinkListTest();
        ListNode[]arr=new ListNode[4];
        ListNode[]arr2=new ListNode[3];
        arr[0]=new ListNode();
        arr[1]=new ListNode();
        arr[2]=new ListNode();
        arr[3]=new ListNode();
        arr2[0]=new ListNode();
        arr2[1]=new ListNode();
        arr2[2]=new ListNode();

        arr[0].val=1;
        arr[0].next=arr[1];
        arr[1].val=4;
        arr[1].next=arr[2];
        arr[2].val=5;
        arr[2].next=arr[3];
        arr[3].val=7;
        arr[3].next=null;

        arr2[0].val=1;
        arr2[0].next=arr2[1];
        arr2[1].val=3;
        arr2[1].next=arr2[2];
        arr2[2].val=6;
        arr2[2].next=null;


        test.isPalindrome(arr[0]);
    }


    /**
     *删除链表的倒数第N个节点
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p=head;
        ListNode p1=p;
        while(p.next!=null){
            p=p.next;
        }
        while(p1.next!=null){
            ListNode t=p1.next;
            for (int i = 0; i < n; i++) {
                t=t.next;
            }
            if(t==p){
               p.next=p.next.next;
               return head;
            }
        }
        return head;
    }


    /**
     * 反转链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
//        if(head.next==null)return null;
//        ListNode p=head;
//        ListNode p1=head.next;
//        while(p1.next!=null){
//            p=p.next;
//            p1=p1.next;
//        }
//        p1.next=p;
//        p.next=null;
//        return  reverseList(head);
          int top=-1;
          int []elements=new int[5000];

        ListNode p=head;
        while(p!=null){
            top++;
            elements[top]=p.val;
            p=p.next;
        }
        p=head;
        while(p!=null){
            p.val=elements[top];
            top--;
            p=p.next;
        }
          return  head;


    }

    /**
     * 合并两个有序链表
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode p1 = l1;
        ListNode p2 = l2;
        ListNode head = new ListNode();
        ListNode temp = head;
        while(p1!=null&&p2!=null){
            if(p1.val<=p2.val){
                temp.next = new ListNode(p1.val);
                p1 = p1.next;
            }else{
                temp.next = new ListNode(p2.val);
                p2 = p2.next;
            }
            temp = temp.next;
        }
        if(p1==null){
            temp.next = p2;
        }else{
            temp.next = p1;
        }
        return head.next;
    }

    /**
     * 回文链表
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        Stack<Integer> stack=new Stack<>();
        ListNode p=head;
        while(p!=null){
            stack.push(p.val);
            p=p.next;
        }
        while(head!=null){
            if(stack.pop()!=head.val)return false;
            head=head.next;
        }
        return true;
    }

    /**
     * 环形链表
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        if (head == null)
            return false;
        //快慢两个指针
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            //慢指针每次走一步
            slow = slow.next;
            //快指针每次走两步
            fast = fast.next.next;
            //如果相遇，说明有环，直接返回true
            if (slow == fast)
                return true;
        }
        //否则就是没环
        return false;
    }
}
